#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

const int SIZE = 128;     //字符集字符数全局定义

//创建模式串的哈希表
void createBC(string SubStr, int* bc)
{
    int i,
        SubLen = SubStr.size();

    //初始化哈希表为-1
    for (i = 0; i < SIZE; ++i)
    {
        bc[i] = -1;
    }

    //存储每个字符在子串的位置
    for (int i = 0; i < SubLen; ++i)
    {
        bc[SubStr[i]] = i;
    }

    for (int i = 0; i < SIZE; ++i)
    {
        if (bc[i] != -1)
        {
            cout << "bc[" << i << "] = " << bc[i] << endl;
        }
    }
    cout << endl;
}

//预处理模式串，填充suffix，prefix
void generateGS(string SubStr, int* suffix, bool* prefix)
{
    int i,
        SubLen = SubStr.size();

    //两个数组初始化
    for (i = 0; i < SubLen; ++i)
    {
        suffix[i] = -1;
        prefix[i] = false;
    }

    for (i = 0; i < SubLen - 1; ++i)
    {
        int j = i,
            len = 0;//公共后缀子串长度(模式串尾部取k个出来，分别比较)

        //与SubStr[0,m-1]求公共后缀子串
        while (j >= 0 && SubStr[j] == SubStr[SubLen - 1 - len])
        {
            j--;
            len++;
            suffix[len] = j + 1;
            //相同后缀子串长度为k时，该子串在SubStr[0,i]中的起始下标
            // (如果有多个相同长度的子串，被赋值覆盖，存较大的)
        }

        //查找到模式串的头部了
        if (j == -1)
        {
            prefix[len] = true;//如果公共后缀子串也是模式串的前缀子串
        }
    }

    for ( i = 0; i < SubLen; i++)
    {
        cout << "suffix[" << i << "]" << suffix[i] << endl;
    }
    cout << endl;

    for (i = 0; i < SubLen; i++)
    {
        cout << "prefix[" << i << "]" << prefix[i] << endl;
    }
    cout << endl;
}

//传入的index是坏字符对应的模式串中的字符下标
int moveByGS(int index, int SubLen, int* suffix, bool* prefix)
{
    //好后缀长度
    int len = SubLen - 1 - index;

    //case1，找到跟好后缀一样的模式子串（多个的话，存的靠后的那个（子串起始下标））
    if (suffix[len] != -1)
    {
        return index - suffix[len] + 1;
    }

    //case2，找不到跟好后缀一样的模式子串，但找得到与好后缀子串一样的模式子串
    for (int i = index + 2; i < SubLen; i++)
    {
        //SubLen - i是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串
        if (prefix[SubLen - i] == true)
        {
            return i;//在上面没有找到相同的好后缀下，移动i位，对齐前缀到好后缀
        }
    }

    //case3，都没有匹配的，移动SubLen位（模式串长度）
    return SubLen;
}

int bm(string MainStr, string SubStr)
{
    int MainLen = MainStr.size();
    int SubLen = SubStr.size();

    int* bc = new int[SIZE];
    int* suffix = new int[SubLen];
    bool* prefix = new bool[SubLen];

    //预处理模式串
    createBC(SubStr, bc);            //构建坏字符哈希表
    generateGS(SubStr,suffix, prefix);         //填充suffix，prefix

    int i = 0,
        moveLen1,
        moveLen2;

    while (i < MainLen - SubLen + 1)
    {
        //j表示主串与模式串匹配的第一个字符
        int j;
        //模式串从后往前匹配
        for (j = SubLen - 1; j >= 0; --j)
        {
            if (MainStr[i + j] != SubStr[j])
            {
                break;  //坏字符对应模式串中的下标是j
            }
        }

        //匹配成功
        if (j < 0)
        {
            delete[] bc;
            delete[] suffix;
            delete[] prefix;
            return i;   //返回主串与模式串第一个匹配的字符的位置
        }

        //这里等同于将模式串往后滑动 j - bc[int(a[i+j])] 位
        moveLen1 = j - bc[int(MainStr[i + j])];     //坏字符规则移动距离
        moveLen2 = 0;
        //如果有好后缀的话
        if (j < SubLen - 1)
        {
            moveLen2 = moveByGS(j, SubLen, suffix, prefix);//按照好后缀规则移动距离
        }
        //取大的移动
        i = i + max(moveLen1, moveLen2);
    }
    delete[] bc;
    delete[] suffix;
    delete[] prefix;
    return -1;
}

int main()
{
    string a = "abcacabcbcbacabc";
    string b = "bcbcba";
    cout << a << "中第一次出现" << b << "的位置(从0开始)是：" << bm(a, b) << endl;
    system("pause");
    return 0;
}

//单个函数版
/*
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

const int SIZE = 128;     //字符集字符数全局定义

int bm(string MainStr, string SubStr)
{
    int MainLen = MainStr.size();
    int SubLen = SubStr.size();

    int* bc = new int[SIZE];
    int* suffix = new int[SubLen];
    bool* prefix = new bool[SubLen];

    int i;

    //预处理模式串

    //创建模式串的哈希表

    //初始化哈希表为-1
    for (i = 0; i < SIZE; ++i)
    {
        bc[i] = -1;
    }

    //存储每个字符在子串的位置
    for (int i = 0; i < SubLen; ++i)
    {
        bc[SubStr[i]] = i;
    }



    //填充suffix，prefix

    //两个数组初始化
    for (i = 0; i < SubLen; ++i)
    {
        suffix[i] = -1;
        prefix[i] = false;
    }

    for (i = 0; i < SubLen - 1; ++i)
    {
        int j = i,
            len = 0;//公共后缀子串长度(模式串尾部取k个出来，分别比较)

        //与SubStr[0,m-1]求公共后缀子串
        while (j >= 0 && SubStr[j] == SubStr[SubLen - 1 - len])
        {
            j--;
            len++;
            suffix[len] = j + 1;
            //相同后缀子串长度为k时，该子串在SubStr[0,i]中的起始下标
            // (如果有多个相同长度的子串，被赋值覆盖，存较大的)
        }

        //查找到模式串的头部了
        if (j == -1)
        {
            prefix[len] = true;//如果公共后缀子串也是模式串的前缀子串
        }
    }



    int moveLen1,
        moveLen2;
    i = 0;
    while (i < MainLen - SubLen + 1)
    {
        //j表示主串与模式串匹配的第一个字符
        int j;
        //模式串从后往前匹配
        for (j = SubLen - 1; j >= 0; --j)
        {
            if (MainStr[i + j] != SubStr[j])
            {
                break;  //坏字符对应模式串中的下标是j
            }
        }

        //匹配成功
        if (j < 0)
        {
            delete[] bc;
            delete[] suffix;
            delete[] prefix;
            return i;   //返回主串与模式串第一个匹配的字符的位置
        }

        //这里等同于将模式串往后滑动 j - bc[int(a[i+j])] 位
        moveLen1 = j - bc[int(MainStr[i + j])];     //坏字符规则移动距离
        moveLen2 = 0;
        //如果有好后缀的话
        if (j < SubLen - 1)
        {
            int index = j;
            //好后缀长度
            int len = SubLen - 1 - index;

            //case1，找到跟好后缀一样的模式子串（多个的话，存的靠后的那个（子串起始下标））
            if (suffix[len] != -1)
            {
                moveLen2 = index - suffix[len] + 1;
            }

            //case2，找不到跟好后缀一样的模式子串，但找得到与好后缀子串一样的模式子串
            for (int k = index + 2; k < SubLen; i++)
            {
                //SubLen - k是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串
                if (prefix[SubLen - k] == true)
                {
                    moveLen2 = k;//在上面没有找到相同的好后缀下，移动k位，对齐前缀到好后缀
                }
            }

            //case3，都没有匹配的，移动SubLen位（模式串长度）
            moveLen2 = SubLen;
        }
        //取大的移动
        i = i + max(moveLen1, moveLen2);
    }
    delete[] bc;
    delete[] suffix;
    delete[] prefix;
    return -1;
}

int main()
{
    string a = "abcacabcbcbacabc";
    string b = "bcbcba";
    cout << a << "中第一次出现" << b << "的位置(从0开始)是：" << bm(a, b) << endl;
    system("pause");
    return 0;
}
*/